home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / source / snip9503 / list.hpp < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-14  |  6.4 KB  |  258 lines
  1. ////////////////////////////////////////////////////////////////
  2. // MODULE
  3. //  list.hpp
  4. // CREATED
  5. //  davidn  03 Dec 1994  23:34
  6. //  David L. Nugent
  7. //  This class implementation is donated to the public domain
  8. // DESCRIPTION
  9. //  Classes supporting linked list containers
  10. // CLASSES/TYPES
  11. //  class node
  12. //    Represents a single link in a doubly linked list
  13. //  class list
  14. //    Base class which handles all of the linked list management
  15. //  class iter
  16. //    Base class for handling iteration through a linked list
  17. //  class Node<T>
  18. //    Template class used for containment of an arbitrary type T
  19. //  class List<T>
  20. //    Linked list class which is used to get/store/remove nodes
  21. //    from a linked list containing data
  22. //  class Iter<T>
  23. //    Used for iteration of a List<T>
  24. // SYNOPSIS
  25. //  These classes allow any arbitrary type to be contained in a
  26. //  type-safe linked list. All of the common code for list
  27. //  management itself is contained in a common set of classes:
  28. //  node, list and iter. Template classes derived from these
  29. //  allow inline access to the underlying base classes via a
  30. //  type-safe front-end.
  31. ////////////////////////////////////////////////////////////////
  32.  
  33. #if !defined( _list_h )
  34. #define _list_h
  35.  
  36. class list;
  37.  
  38.     // Generic 'node' class
  39.  
  40. class node
  41. {
  42.     friend class iter;
  43.   public:
  44.     node( list * L =0, node * prv =0, node * nxt =0 )
  45.       : mylist( 0 ), Prev( 0 ), Next( 0 )
  46.     { link( L, prv, nxt ); }
  47.     virtual ~node( void )
  48.     { unlink( ); }
  49.     void link( list * L, node * prv, node * nxt );
  50.     void unlink( );
  51.     node * prevNode( void ) const
  52.     { return Prev; }
  53.     node * nextNode( void ) const
  54.     { return Next; }
  55.   private:
  56.     list * mylist;
  57.     node * Prev, * Next;
  58. };
  59.  
  60.     // template node frontend
  61.  
  62. template<class T>
  63. class Node : public node
  64. {
  65.   public:
  66.     Node( T data, list * L =0, node * prv =0, node * nxt =0 )
  67.       : node( L, prv, nxt ), Data( data ) {}
  68.     Node<T> * next( void ) const
  69.     { return (Node<T> *)nextNode(); }
  70.     Node<T> * prev( void ) const
  71.     { return (Node<T> *)prevNode(); }
  72.     T & ref2data( void ) const
  73.     { return ( T & )Data; }
  74.     T * ptr2data( void ) const
  75.     { return ( T * )&Data; }
  76.     T data( void ) const
  77.     { return Data; }
  78.   private:
  79.     T Data;
  80. };
  81.  
  82.     // Generic 'list' class
  83.  
  84. class list
  85. {
  86.     friend class node;
  87.   public:
  88.     list( void )
  89.       : First( 0 ), Last( 0 ), nodes( 0 ) {}
  90.     virtual ~list( void )
  91.     { purge(); }
  92.     void purge( void );
  93.     long items( void ) const
  94.     { return nodes; }
  95.     void addatstart( node * n )
  96.     { n->link( this, 0, First ); }
  97.     void addatend( node * n )
  98.     { n->link( this, Last, 0 ); }
  99.     void addafter( node * n, node * prv )
  100.     { n->link( this, prv, 0 ); }
  101.     void addbefore( node * n, node * nxt )
  102.     { n->link( this, 0, nxt ); }
  103.     node * firstNode( void ) const
  104.     { return First; }
  105.     node * lastNode( void ) const
  106.     { return Last; }
  107.   protected:
  108.     node * First, * Last;
  109.     long nodes;
  110. };
  111.  
  112.     // Container class List<T>
  113.  
  114. template<class T>
  115. class List : public list
  116. {
  117.   public:
  118.     List( void ) : list() {}
  119.     Node<T> * add( T data, Node<T> * prv =0, Node<T> * nxt =0 )
  120.     { return new Node<T>( data, this, prv, nxt ); }
  121.     Node<T> * first( void ) const
  122.     { return (Node<T> *)First; }
  123.     Node<T> * last( void ) const
  124.     { return (Node<T> *)Last; }
  125. };
  126.  
  127. enum trOp
  128. {
  129.   FIRST, LAST, PREV, NEXT, CURR
  130. };
  131.  
  132. #define TR_OK     0
  133. #define TR_EMPTY  -2
  134. #define TR_NOMORE -3
  135.  
  136. class iter
  137. {
  138.   public:
  139.     iter( list & L )
  140.       : mylist( L ), nptr( 0 ) {}
  141.     iter( iter const & I )
  142.       : mylist( I.mylist ), nptr( I.nptr ) {}
  143.     iter & operator=( iter const & I )
  144.     { if ( &I.mylist == &mylist ) nptr = I.nptr; return *this; }
  145.     void reset( void )
  146.     { nptr = 0; }
  147.     int traverse( trOp op );
  148.     int current( void )
  149.     { return traverse( CURR ); }
  150.     int first( void )
  151.     { return traverse( FIRST ); }
  152.     int last ( void )
  153.     { return traverse( LAST );  }
  154.     int prev( void )
  155.     { return traverse( PREV );  }
  156.     int next( void )
  157.     { return traverse( NEXT );  }
  158.   protected:
  159.     list & mylist;
  160.     node * nptr;
  161. };
  162.  
  163.     // Iterator
  164.  
  165. template<class T>
  166. class Iter : public iter
  167. {
  168.   public:
  169.     typedef int (*comparator)( const &T, const T&);
  170.  
  171.     Iter( List<T> & L )
  172.       : iter( L ) {}
  173.     Iter( Iter<T> const & I )
  174.       : iter( I ) {}
  175.     Iter<T> & operator=( Iter<T> const & I )
  176.     { iter::operator=( I ); return *this;  }
  177.     List<T> & myList( void ) const
  178.     { return ( List<T> & )mylist; }
  179.     Node<T> * atNode( void ) const
  180.     { return ( Node<T> * )nptr; }
  181.     T & ref2data( void ) const
  182.     { return atNode()->ref2data(); }
  183.     T * ptr2data( void ) const
  184.     { return atNode()->ptr2data(); }
  185.     T data( void ) const
  186.     { return atNode()->data(); }
  187.     void addFirst( T data )
  188.     { myList().addatstart( new Node<T>( data ) ); }
  189.     void addLast( T data )
  190.     { myList().addatend( new Node<T>( data ) ); }
  191.     void addAfter( T data )
  192.     { myList().addafter( new Node<T>( data ), nptr ); }
  193.     void addBefore( T data )
  194.     { myList().addbefore( new Node<T>( data ), nptr ); }
  195.     void add( T data, trOp op );
  196.     trOp locate( T & data, comparator compare );
  197.     int addsorted( T data, comparator compare ),
  198.                    int adddupe =0 );
  199. };
  200.  
  201. template<class T> void Iter<T>::add( T data, trOp op )
  202. {
  203.   switch( op )
  204.   {
  205.   case FIRST:           addFirst( data );    break;
  206.   case LAST:            addLast( data );     break;
  207.   case PREV:            addBefore( data );   break;
  208.   case CURR: case NEXT: addAfter( data );    break;
  209.   }
  210. }
  211.  
  212. template<class T>
  213. trOp
  214. Iter<T>::locate( T & data, comparator compare )
  215. {
  216.   register trOp rc;
  217.   register Node<T> * n = myList().first();
  218.  
  219.   if ( n == 0 )   // Add to start of empty list
  220.     rc = FIRST;
  221.   else
  222.   {
  223.     rc = LAST;
  224.     while ( rc == LAST && n != 0 )
  225.     {
  226.       int r = compare( data, n->ref2data() );
  227.       if ( r == 0 )       // Found an exact match
  228.         rc = CURR;
  229.       else if ( r < 0 )   // We've gone past it
  230.         rc = PREV;
  231.       else
  232.         n = n->next();
  233.     }
  234.   }
  235.  
  236.   nptr = n;
  237.   return rc;
  238.  
  239. }
  240.  
  241. template<class T>
  242. int
  243. Iter<T>::addsorted( T data, comparator compare ),
  244.                     int adddupe )
  245. {
  246.   trOp r;
  247.  
  248.   if ((( r  = locate( data, compare )) != CURR ) || adddupe )
  249.   {
  250.     add( data, r );
  251.     return 1;
  252.   }
  253.   return 0;
  254. }
  255.  
  256. #endif    // _list_h
  257.  
  258.